package sliding_window

import (
	"math/bits"
	"unicode"
)

/*

当一个字符串 s包含的每一种字母的大写和小写形式 同时出现在 s中，就称这个字符串s是 美好 字符串。
比方说，"abABB"是美好字符串，因为'A' 和'a'同时出现了，且'B' 和'b'也同时出现了。然而，"abA"不是美好字符串因为'b'出现了，而'B'没有出现。

给你一个字符串s，请你返回s最长的美好子字符串。如果有多个答案，请你返回最早出现的一个。如果不存在美好子字符串，请你返回一个空字符串。

示例 1：
输入：s = "YazaAay"
输出："aAa"
解释："aAa" 是一个美好字符串，因为这个子串中仅含一种字母，其小写形式 'a' 和大写形式 'A' 也同时出现了。
"aAa" 是最长的美好子字符串。

示例 2：
输入：s = "Bb"
输出："Bb"
解释："Bb" 是美好字符串，因为 'B' 和 'b' 都出现了。整个字符串也是原字符串的子字符串。

示例 3：
输入：s = "c"
输出：""
解释：没有美好子字符串。

示例 4：
输入：s = "dDzeE"
输出："dD"
解释："dD" 和 "eE" 都是最长美好子字符串。
由于有多个美好子字符串，返回 "dD" ，因为它出现得最早。
*/

// 枚举|位运算
//时间复杂度：O(n^2) 其中 n 为字符串的长度。需要枚举所有可能的子字符串，因此需要双重循环遍历字符串，总共可能有 n^2个连续的子字符串。
//空间复杂度：O(1) 由于返回值不需要计算空间复杂度，除了需要两个整数变量用来标记以外不需要额外的空间。

//两层for循环记录字符串的起点i和重点j,判断字符串[i,j]是否满足每一种字母的大写和小写形式【同时】出现。
//在移动j的时候，维护两个变量up和low,分别表示大写字母出现了哪些，小写字母出现了哪些：
// up |= (s[j]-'A')(如果s[j]是大写字母) , low |= (s[j] - 'a')(如果s[j]是小写字母)
//如果最后 up==low 即表示字符串[i,j]中每一种字母的大写和小写形式同时出现
func longestNiceSubstring(s string) (ans string) {
	for i := range s {
		lower, upper := 0, 0
		for j := i; j < len(s); j++ {
			if unicode.IsLower(rune(s[j])) {
				lower |= 1 << (s[j] - 'a') //16777217类似数据
			} else {
				upper |= 1 << (s[j] - 'A')
			}
			if lower == upper && j-i+1 > len(ans) { // lower==upper==1
				ans = s[i : j+1]
			}
		}
	}
	return
}

//分治法
//如果字符串本身即合法的美好字符串，此时最长的完美字符串即为字符串本身。
//由于字符串中含有部分字符 ch 只出现大写或者小写形式，如果字符串包含这些字符 ch 时，可以判定该字符串肯定不为完美字符串。
//一个字符串为美好字符串的必要条件是不包含这些非法字符。因此我们可以利用分治的思想，将字符串从这些非法的字符处切分成若干段
//则满足要求的最长子串一定出现在某个被切分的段内，而不能跨越一个或多个段。

//本题中字符串仅包含英文大小写字母，因此 Σ∣=52。
//空间复杂度：O(∣Σ∣)。由于递归深度最多为 ∣Σ∣，因此需要使用 O(∣Σ∣) 的递归栈空间
func longestNiceSubstring1(s string) (ans string) {
	if s == "" {
		return
	}
	lower, upper := 0, 0
	for _, ch := range s {
		if unicode.IsLower(ch) {
			lower |= 1 << (ch - 'a') //50331649 1
		} else {
			upper |= 1 << (ch - 'A') //16777217
		}
	}
	if lower == upper {
		return s
	}

	valid := lower & upper //16777217
	for i := 0; i < len(s); i++ {
		start := i
		for i < len(s) && valid>>(unicode.ToLower(rune(s[i]))-'a')&1 == 1 {
			i++
		}
		if t := longestNiceSubstring1(s[start:i]); len(t) > len(ans) {
			ans = t
		}

	}
	return
}

//滑动窗口
//对于给定的字符种类数量typeNum,我们维护滑动窗口的左右边界l,r,滑动窗口内部大小字符出现的次数upperCnt和lowerCnt,以及滑动窗口内的字符种类数量total
//当total>typeNum时我们不断右移左边界l,并对应地更新upperCnt,lowerCnt以及total,直到total<= typeNum为止。这样，对于任何一个右边界r,我们都能找到
//最小的l(记为lmin,使得s[lmin...r])之间的字符数目不多于typeNum)

//最长的完美字符串一定出现在某个窗口中。判断当前s[lmin..r]是否为完美字符串，检测方法如下:
//当前字符串中的字符种类数量为typeNum,当前字符串中同时出现大小写的字符的种类数量为cnt,只有满足cnt==typeNum时，我们可以判定字符串为完美字符串
//遍历upperCnt，lowerCnt两个数组，第i个字符同时满足upperCnt[i]>0,lowerCnt[i]>0时，则认为第i个字符的大小写形式同时出现
//结论：当限定字符种类数目为typeNum时，满足题意的最长子串，就一定出自某个s[lmin...r],因此在滑动窗口维护过程中，就可以直接得到最长子串的大小。
//时间复杂度：O(N⋅∣Σ∣)，其中 N 为字符串的长度。∣Σ∣ 为字符集的大小，本题中字符集限定为大小写英文字母，∣Σ∣=52
//空间复杂度：O(∣Σ∣)。需要 O(∣Σ∣) 存储所有大小写字母的计数
func longestNiceSubstring2(s string) (ans string) {

	//取得字符串中字符的种类个数 start
	mask := uint(0)
	for _, ch := range s {
		mask |= 1 << (unicode.ToLower(ch) - 'a') //按照小写字母为标准
	}
	//取得字符种类
	maxTypeNum := bits.OnesCount(mask)
	//取得字符串中字符的种类个数 end

	for typeNum := 1; typeNum <= maxTypeNum; typeNum++ {
		//中间变量：记录大小写字符出现的次数
		var lowerCnt, upperCnt [26]int

		//滑动窗口内字符种类数量，同时出现大小写字符的种类数量，左指针
		var total, cnt, l int

		//滑动窗口
		for r, ch := range s {

			//统一根据小写字母计算下标值
			idx := unicode.ToLower(ch) - 'a' //找到26个英文字母数组的下标值

			//如果是小写字母
			if unicode.IsLower(ch) {
				lowerCnt[idx]++
				if lowerCnt[idx] == 1 && upperCnt[idx] > 0 {
					//同时出现大小写的字符的种类数量
					cnt++
				}
			} else {
				//如果是大写字母
				upperCnt[idx]++
				if upperCnt[idx] == 1 && lowerCnt[idx] > 0 {
					//同时出现大小写的字符的种类数量
					cnt++
				}
			}
			//表示新增了一种字符
			if lowerCnt[idx]+upperCnt[idx] == 1 {
				total++
			}

			//如果字符数量大于字符类型数量, 进行窗口缩放
			//-------------------对称操作---------------------
			for total > typeNum {

				idx := unicode.ToLower(rune(s[l])) - 'a' //以小写字母为标准

				//窗口内字符种类数量减一
				if lowerCnt[idx]+upperCnt[idx] == 1 {
					total--
				}

				//如果是小写字母
				if unicode.IsLower(rune(s[l])) {
					lowerCnt[idx]--
					if lowerCnt[idx] == 0 && upperCnt[idx] > 0 {
						//同时出现大小写的字符的种类数量-1
						cnt--
					}
				} else {
					upperCnt[idx]--
					if upperCnt[idx] == 0 && lowerCnt[idx] > 0 {
						//同时出现大小写的字符的种类数量-1
						cnt--
					}
				}
				l++
			}

			//同时出现大小写的字符的种类数量=类型数量
			if cnt == typeNum && r-l+1 > len(ans) {
				ans = s[l : r+1]
			}
		}
	}
	return
}

//前缀和(*********此方法没有验证通过**********)
//遍历字符串，预处理前缀和数组 sum[i][j]，表示字符串 s 的前 i个字符，每个字符 j 出现的次数。
//时间复杂度：O(26 n^2)
//空间复杂度：O(1)
func longestNiceSubstring3(s string) string {
	//初始化二维数组
	row := len(s) + 1
	col := 256
	sum := make([][]int, row)

	for r := range sum {
		sum[r] = make([]int, col)
	}

	for i := 0; i < len(s); i++ {
		//复制行数据
		sum[i+1] = sum[i]
		//字符串s的前i+1个字符，每个字符 s[i]-'A' 出现的次数
		sum[i+1][unicode.ToUpper(rune(s[i]))-'A'] += 1
	}

	maxLength, id := 0, -1

	for i := 0; i < len(s); i++ {
		for j := i + 1; j < len(s); j++ {
			//判断出现的次数
			flag := true

			//判断26个字母中是否有大小写重复的
			for c := 0; c < 26; c++ {
				up := sum[j+1][c] - sum[i][c]
				low := sum[j+1][c+32] - sum[i][c+32]

				if up == 0 && low != 0 {
					flag = false
				}

				if up != 0 && low == 0 {
					flag = false
				}
			}

			//如果大小写都出现了
			if flag && j-i+1 > maxLength {
				maxLength = j - i + 1
				id = i
			}
		}
	}
	if maxLength == 0 {
		return ""
	}

	return s[id : id+maxLength]
}
